package answer_11_20

import (
	"fmt"
	"sort"
)

//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//返回这三个数的和。
//假定每组输入只存在恰好一个解。

//示例 1：
//输入：nums = [-1,2,1,-4], target = 1

//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

//示例 2：
//输入：nums = [0,0,0], target = 1
//输出：0

//解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

//提示：
//3 <= nums.length <= 1000
//-1000 <= nums[i] <= 1000
//-104 <= target <= 104

func Answer_16() {
	fmt.Println(threeSumClosest_1([]int{10, 20, 30, 40, 50, 60, 70, 80, 90}, 1))
}

func threeSumClosest_1(nums []int, target int) int {
	sort.Ints(nums)
	n, SumClosest := len(nums), nums[0]+nums[1]+nums[2] // 初始化为前三元素的值
	for i := 0; i < n-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		j, k := i+1, n-1
		for j < k {
			sum := nums[i] + nums[j] + nums[k]
			if sum == target {
				return target
			}
			if abs(sum-target) < abs(SumClosest-target) {
				SumClosest = sum
			}
			if sum > target {
				k--
			} else {
				j++
			}
		}
	}
	return SumClosest
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
